
%%% Preamble
\documentclass[paper=a4, fontsize=11pt]{scrartcl}	% Article class of KOMA-script with 11pt font and a4 format
\typearea{12}
\usepackage[T1]{fontenc}
\usepackage{fourier}
\usepackage{CJKutf8} 
\newcommand{\jap}[1]{\begin{CJK}{UTF8}{min}#1\end{CJK}}

\usepackage[english]{babel}															% English language/hyphenation
\usepackage[protrusion=true,expansion=true]{microtype}	% Better typography
\usepackage{amsmath,amsfonts,amsthm}
% Math packages
\usepackage[pdftex]{graphicx}														% Enable pdflatex
\usepackage{url}
% Graphics packages
%\usepackage{caption}
\usepackage{subcaption}


%%% Custom sectioning (sectsty package)
\usepackage{sectsty}	% Custom sectioning (see below)
%\allsectionsfont{\centering \normalfont\scshape} % Change font of al section commands


%%% Custom headers/footers (fancyhdr package)
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\fancyhead[C]{DD2380 Artificial Intelligence}														% No page header
\fancyfoot[L]{}		% You may remove/edit this line 
\fancyfoot[C]{}													% Empty
\fancyfoot[R]{\thepage}									% Pagenumbering
\renewcommand{\headrulewidth}{0pt}			% Remove header underlines
\renewcommand{\footrulewidth}{0pt}				% Remove footer underlines
\setlength{\headheight}{13.6pt}


%%% Equation and float numbering
%\numberwithin{equation}{section}		% Equationnumbering: section.eq#
%\numberwithin{figure}{section}			% Figurenumbering: section.fig#
%\numberwithin{table}{section}				% Tablenumbering: section.tab#


%%% Maketitle metadata
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} 	% Horizontal rule

\title{
		%\vspace{-1in} 	
		\usefont{OT1}{bch}{b}{n}
		\normalfont \normalsize \textsc{KTH - Kungliga Tekniska H\"ogskolan} \\ [25pt]
		\horrule{0.5pt} \\[0.4cm]
		\huge Solving the Sokoban Game \\
		\horrule{2pt} \\[0cm]
}


%%% Begin document
\begin{document}
\maketitle
\date{}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.5]{portraits.png}
\caption{Group members: From left to right and top to bottom: Martin Engelberge (930118), Robert Tordel\"ov (900122); Florian Vincent Depraz (931108), Anton Lund (890313)}
\end{center}
\end{figure}

%%%abstract
\abstract{Abstract: blablabla.}

\newpage
\section{Introduction}
The purpose of this report is to give a short introduction to the game called Sokoban and then continue to describe our implementation of an AI capable of solving the game. We will start by describing our approach to solving the game conceptually and then move on to the specifics of our implementation. We will then present the results from our solution by reporting the feedback form Kattis as well as testing with different search algorithm such as BFS or DFS. We will then move on to a discussion of our solver in general, we could be improved and what could be done differently.
Our project group consists of 4 members. Two of the members have computer science backgrounds while two students are have an Engineering Physics program. The work of designing the overall program has been done in the group as a whole. We have together discussed what problems to look out for and to solve them conceptually. Group members have then spent different times on different parts of the project. Some have spent more time implementing code while others have spent more time on the project report.

\subsection{History}

Sokoban is a 2-dimensional computer game created in 1981 by Hiroyuki Imabayashi at \jap{シンキングラビット} (Thinking Rabbit). The name of the game \jap{倉庫番} (s\=okoban) means warehouse keeper. Since the original implementation for NEC PC-8801, Sokoban has been ported to a wide number of platforms and has also due to the complexity of the game been a subject of much research.  The problem of solving the game has been proved do be NP-hard and PSPACE-complete. Solving the game has important real-life implementations as the solution model could be used to for example design a robot working in a warehouse. There seems to be so far no solver that is capable of solving any sokoban map.

\subsection{Game Concept and Rules}

In sokoban, you play a warehouse keeper tasked with moving boxes in a warehouse to specifically designated areas. The game is played on a grid and the Sokoban world consists of 4 element: player, walls, boxes, goals and spaces. All nodes in the grid can only be occupied by one box at a time and a node with no element is a space. The game is won when all boxes are placed on a goal node.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.45]{sokoban1.png}
\caption{An example of a Sokoban map. Image source: course website}
\end{center}
\end{figure}

The difficulties in solving Sokoban rises from both the high branching factor (comparable to chess) as well as a very deep tree level. It is also a difficult to game to solve by trial and error with low search depth as the game can reach so called 'deadlocks'. A deadlock is a state of the game from which there is no possible solution. An example of a deadlock is a box in a corner as there is no way to get the box out of that corner.
If the AI does not have an efficient way of evaluating deadlock states, it is possible that the search algorithm enters an infinite loop. There is however no perfect method for evaluating if any state is a deadlock or not.
\section{Solution}

Writing an algorithm that could theoretically solve a game like Sokoban is trivial. The difficulty is solving the problem in a reasonable time and using a reasonable amount of resources. Much of what constitutes our solution to the problem, is different methods for saving time and resources by limiting the search tree, using efficient data structure and implementing fast search algorithm.

\subsection{Representation}
An important aspect of the search tree is how to construct a search node. You want each search node to be as small as possible while still containing all the information you need. What is however maybe most important for efficiency is to keep the amount of nodes as small as possible. This can be done by preventing overlap between nodes, that is making sure that there are no repeated states in the search tree.

An important factor that needs to be taken into account for decreasing the resources needed for each search node is by distinguishing between  dynamic and static aspects of the game. In the Sokoban concept, the game map is essentially a static object so there is no need to include the whole of the map in the memory for each game state. Instead by saving the static goals and walls as a game object, we only have to take into account the boxes and the player for each gamestate. A full representation of the state can then be created by superimposing the boxes and the player on the static map.

When a human would play this game, he could for example move up to a box, consider whether to move the box or not. If he decides not to move that box, he could move up to another box and do the same. The observation you can make here is that by simply moving around without moving boxes, he has not limited his future possible box moves in any way. 

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.4]{sokoban2.png}
\caption{Showing the concept of player area. Image source: edited version of image from course website.}
\end{center}
\end{figure}

The figure above shows a Sokoban map, where all tiles the player can reach without moving a box are highlighted with gray color and is what we define as the player area. The objective of the game is as stated above to get all boxes onto goal tiles. While only moving inside the player area, we have not changed the position of the boxes, or the way we can interact with them and there is thus no need for seperating between different positions of the player inside this area.

To fulfill our objective of buildling a search tree as efficient as possible we decided to define a game state as the \textit{position of the boxes} and the \textit{area a player can reach without moving any boxes}. This of course allocates more resources for any specific state compared to for example defining a game state by the box positions and the player position. However we believe the resources saved by decreasing the number of states outweighs this.

\subsection{Deadlocks}

To prevent getting deep into branches where the game has become unsolvable, it is important to quickly recognize and prune deadlock states. In our solution, we distinguish between two classes of deadlocks, static and dynamic deadlocks. Static deadlocks are static in the sense that, for each map, they constitute a set of tiles a box should never be pushed to. Such tiles are for example corner tiles and some cases of tiles adjacent to walls as can be seen in (a) of figure 3. Static deadlocks can be identified when the map is initially read so as to never put states with boxes in these positions in the search queue.

\begin{figure}[ht]
\centering
\begin{subfigure}{.49\textwidth}
\includegraphics[width=.46\linewidth]{deadlockstat.png} \centering
\caption{Examples of static deadlocks}
\end{subfigure}

\begin{subfigure}{.49\textwidth}
\includegraphics[width=.60\linewidth]{deadlockdyn.png} \centering
\caption{Examples of dynamic deadlocks. }
\end{subfigure}
\caption{Showing the two classes of deadlocks. Legend (\# - wall, \$ - box, . - goal and * - box on goal)}
\end{figure}

Identifying dynamic deadlocks constitute a much more complicated problem. These kind of deadlocks depend on the dynamic aspects typically patterns of boxs and walls. (b) of figure 3 shows a few typical examples of dynamic deadlocks such as placing two boxes next to eachother adjacent to a wall  or pushing two boxes into a narrow corridor. This existence of these needs to be checked for each gamestate and as the examples in figure 3 show, the patterns can be quite large in size.

It does not seem possible to write a program that could find all possible deadlocks. If a deadlock can not be identified with for example patterns, you would have to prove that the game is unsolvable from that state and that implies you have to effectively expand all possible children states. As this is not advisable you need some kind of function to cut the search if you have searched too deep.

\subsection{Search algorithm}
Another factor that has great influence on performance is the search algorithm. For other than trivially simple maps, searching through all unique possible gamestates is not feasible. There is thus a need to be able to prioritize between branches and also cut off those branches that are not likely to lead to the goal state.

We have thus decided to implement the A* Search Algorithm. The A* algorithm is a pathfinding algorithm that uses a best-first search to find the least-cost path to some kind of goal. Under certain conditions and using a good heuristic, you can prove that the A* algorithm is both complete and optimal.

\subsection{Heuristic}
A* is different form breadth-first search and depth-first search as it is an informed search algorithm. This implies that it uses knowledge of the game to improve the search. As the A* algorithm uses a priority queue to first expand the nodes that seem the most likely, we need to develop some kind of heuristic function to evaluate nodes.
The heuristic function contains two components
\begin{itemize}
\item Past-cost function - Should add a cost that is increasing with the depth of the node.
\item Future-cost function - Should give a good estimation of the distance to the goal.
\end{itemize}
A benefit from using a heuristic with a past-cost rather than a greedy best-first search is that we can avoid search too deep into deadlock states. If future-cost function would lead the search to a deadlock, the accumulation form the past-cost function would eventually start searching other branches. If the past-cost is too strong a factor, the search algorithm would however turn into a simple BFS algorithm.

\section{Implementation}

\subsection{Program Design}

\subsubsection{GameState class}

\subsubsection{Main class}


\section{Results}


\section{Discussion}

\subsection{Other possible features to implement}
As the time limit of this project was rather limited, we did not have time to implement all features we came up with. It should definitely be possible to improve the efficiency and speed of the program by implementing other features. This section will discuss a selection of other possible features:
\begin{itemize}
\item Backwards search - Instead defining the game backwards, by originally placing all boxes in goal areas and pulling boxes backwards until all boxes are on the start positions
\item Bi-directional search - S
\
\

\end{itemize}

\section{References}	


%%% End document
\end{document}